In a binary search tree, the keys on the same level from left to right must be in sorted (non-decreasing) order. (3分)
In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. (3分)
If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (3分)
For a sequentially stored linear list of length , the time complexities for deleting the first element and inserting the last element are and , respectively. (3分)
and have the same speed of growth. (3分)
The recurrent equations for the time complexities of programs P1 and P2 are:
Then the correct conclusion about their time complexities is: (5分)
The result of performing three DeleteMin operations in the min-heap {1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} is: (5分)
Given a directed graph G=(V, E) where V = {v1, v2, v3, v4, v5, v6}
and E = {<v1,v2>, <v1,v4>, <v2,v6>, <v3,v1>, <v3,v4>, <v4,v5>, <v5,v2>, <v5,v6>}
. Then the topological order of G is: (5分)
Which of the following statements is TRUE about topological sorting? (5分)
To delete p
from a doubly linked list, we must do: (6分)
In-order traversal of a binary tree can be done iteratively. Given the stack operation sequence as the following:
push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()
Which one of the following statements is TRUE? (6分)
Given a quadtree(四叉树) with 2 nodes of degree 2, 3 nodes of degree 3, 4 nodes of degree 4. The number of leaf nodes in this tree is __. (5分)
The array representation of a disjoint set is given by { 4, 6, 5, 2, -3, -4, 3 }. If the elements are numbered from 1 to 7, the resulting array after invoking Union(Find(7),Find(1))
with union-by-size and path-compression is: (5分)
If an undirected graph G = (V, E) contains 7 vertices. Then to guarantee that G is connected in any cases, there has to be at least __ edges. (6分)
Insert { 5, 11, 13, 1, 3, 6 } one by one into an initially empty binary search tree. The post-order traversal sequence of the resulting tree is: (6分)
Suppose that an array of size m
is used to store a circular queue. If the head pointer front
and the current size variable size
are used to represent the range of the queue instead of front
and rear
, then the maximum capacity of this queue can be: (5分)
How many leaf node does a complete binary tree with 2435 nodes have? (6分)
The function is to find the K
-th smallest element in a list A
of N
elements. The function BuildMaxHeap(H, K)
is to arrange elements H[1]
... H[K]
into a max-heap. Please complete the following program.
ElementType FindKthSmallest ( int A[], int N, int K )
{ /* it is assumed that K<=N */
ElementType *H;
int i, next, child;
H = (ElementType *)malloc((K+1)*sizeof(ElementType));
for ( i=1; i<=K; i++ ) H[i] = A[i-1];
BuildMaxHeap(H, K);
for ( next=K; next<N; next++ ) {
H[0] = A[next];
if ( H[0] < H[1] ) {
for ( i=1; i*2<=K; i=child ) {
child = i*2;
if ( child!=K && (5分) ) child++;
if ( (5分) )
H[i] = H[child];
else break;
}
H[i] = H[0];
}
}
return H[1];
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 5 |
1 | 答案正确 | 5 |
Please fill in the blanks in the program which performs Find
as a Union/Find operation with path compression.
SetType Find ( ElementType X, DisjSet S )
{
ElementType root, trail, lead;
for ( root = X; S[root] > 0; (5分) ) ;
for ( trail = X; trail != root; trail = lead ) {
lead = S[trail] ;
(5分);
}
return root;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 5 |
1 | 答案正确 | 5 |